#include <iostream>

using namespace std;

typedef long long LL; // 防爆int

LL qmi(int a, int b, int p) {
    // 将幂b转化位二进制,以达到将计算幂O(n)优化到O(logn)的效果~
    
	LL res = 1 % p; // 初始化答案为1
	
	while (b) { // 将b每一位都拿出来判断或计算
		if (b & 1) res = res * a % p; // 如果b的二进制的该位上为1,则说明要用来计算
		                    // 即将 res 更新为 res * a 并 % p (同余定理防止答案溢出)
		a = a * (LL)a % p; // 每次将 a 更新为 上一次a的乘方
		b >>= 1; // 将b右移一位,以将b的二进制的每一位都遍历一遍
	}
	return res; // 返回答案
}

int main() {
	int n;
	scanf("%d", &n);
	while (n -- ) {
		int a, b, p;
		scanf("%d%d%d", &a, &b, &p);
		printf("%lld\n", qmi(a, b, p));
	}
	
	return 0;
}